package LeetCode;

import java.util.ArrayList;

public class LC_514_FreedomTrail {

    public static void main(String[] args) {

    }

    public class Solution {


        @SuppressWarnings("unchecked")
        public int findRotateSteps(String ring, String key) {
            ArrayList<Integer>[] list = new ArrayList[128];
            char ch;
            for (int i = 0; i < ring.length(); i++) {
                ch = ring.charAt(i);
                if (list[ch] == null) {
                    list[ch] = new ArrayList<>();
                }
                list[ch].add(i);
            }
            int ringLoop = ring.length();
            int[][] dp = new int[key.length()][ring.length()];
            for (Integer index : list[key.charAt(0)])
                dp[0][index] = Math.min(index, ringLoop - index);
            char former = key.charAt(0), cur;
            for (int i = 1; i < key.length(); i++) {
                cur = key.charAt(i);
                for (Integer indexCur : list[cur]) {
                    dp[i][indexCur] = Integer.MAX_VALUE;
                    for (Integer indexFormer : list[former]) {
                        int distance = Math.abs(indexCur - indexFormer);
                        dp[i][indexCur] = Math.min(dp[i][indexCur], dp[i - 1][indexFormer] + Math.min(distance, ringLoop - distance));
                    }
                }
                former = cur;
            }
            int mindist = Integer.MAX_VALUE;
            int depth = key.length() - 1;
            for (Integer lastIndex : list[key.charAt(depth)]) {
                if (mindist > dp[depth][lastIndex]) {
                    mindist = dp[depth][lastIndex];
                }
            }
            return mindist + key.length();
        }

    }
}